package leetcode;
import java.util.*;
/**
 * 93.复原IP地址
 * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
 * 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
 * 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入'.' 来形成。
 * 你 不能重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
 *
 * 输入：s = "25525511135"
 * 输出：["255.255.11.135","255.255.111.35"]
 *
 * 输入：s = "0000"
 * 输出：["0.0.0.0"]
 *
 * 输入：s = "101023"
 * 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
 */
public class Num_93 {

    List<Integer> inner = new ArrayList<>();
    List<String> outter = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        dfs(s, 0);
        return outter;
    }

    //递归函数(字符串, 字符串起始位置)
    private void dfs(String s, int startIndex) {
        //边界条件
        if(inner.size() == 4){
            if(startIndex < s.length()){
                //此时，字符串还没用完，不符合条件直接退出
                return;
            }else{
                //此时，字符串已经用完，符合条件
                outter.add(toString(inner));
                return;
            }
        }

        //确保整数是三位即可，[startIndex, i]
        for (int i = startIndex; i < s.length() && i < startIndex + 3; i++) {
            //先把子字符串分割出来
            String sub = s.substring(startIndex, i + 1);
            //转化为整数
            int num = Integer.parseInt(sub);
            //再将整数转回字符串，对比两条字符串的长度，以判断是否含有前导0
            String sub2 = String.valueOf(num);
            //确保合法：255以内 && 不能含有前导0
            if(num <= 255 && sub.length() == sub2.length()){
                inner.add(num);
                dfs(s, i + 1);
                inner.remove(inner.size() - 1);
            }
        }
    }

    //将整型数组转化为IP字符串
    private String toString(List<Integer> inner) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < inner.size() - 1; i++) {
            sb.append(inner.get(i));
            sb.append(".");
        }
        sb.append(inner.get(inner.size() - 1));
        return sb.toString();
    }
}
